#include <bit/stdc++.h>

using namespace std;

// 相邻字符不同的最长路径
// 给你一棵 树（即一个连通、无向、无环图），根节点是节点 0
// 这棵树由编号从 0 到 n - 1 的 n 个节点组成
// 用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树
// 其中 parent[i] 是节点 i 的父节点
// 由于节点 0 是根节点，所以 parent[0] == -1
// 另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符
// 请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径
// 并返回该路径的长度
// 测试链接 : https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/

class Solution 
{
private:
    struct Info
    {
        int maxPathFromHead; // 一定要从头节点出发的情况下，相邻字符不等的最长路径长度
		int maxPath; // 整棵树上，相邻字符不等的最长路径长度
        
        Info(int a, int b) 
        {
			maxPathFromHead = a;
			maxPath = b;
		}
    };

    Info f(string& s, vector<vector<int>>& g, int u)
    {
        // u节点是叶
        if(g[u].empty()) return Info(1, 1);
        int max1 = 0; // 下方最长链
        int max2 = 0; // 下方次长链
        int maxPath = 1;
        for(int v : g[u])
        {
            Info&& nextInfo = f(s, g, v);
            maxPath = max(maxPath, nextInfo.maxPath);
            if(s[u] != s[v])
            {
                if(nextInfo.maxPathFromHead > max1)
                {
                    max2 = max1;
                    max1 = nextInfo.maxPathFromHead;
                }
                else if(nextInfo.maxPathFromHead > max2)
                {
                    max2 = nextInfo.maxPathFromHead;
                }
            }
        }
        int maxPathFromHead = max1 + 1;
        maxPath = max(maxPath, max1 + max2 + 1);
        return Info(maxPathFromHead, maxPath);
    }

public:
    int longestPath(vector<int>& parent, string s) 
    {
        int n = parent.size();
        vector<vector<int>> g(n);
        for(int i = 1; i < n; ++i) g[parent[i]].push_back(i);
        return f(s, g, 0).maxPath;
    }
};



class Solution 
{
public:
    int longestPath(vector<int>& parent, string s) 
    {
        int n = parent.size();
        vector<vector<int>> g(n);
        for(int i = 1; i < n; ++i) g[parent[i]].push_back(i);

        // ret 记录的是整棵树的相邻节点字符不相等最长链的长度
        int ret = 0;
        // dfs(x) 的返回值是以 x 为头时，相邻节点字符不相同的最长链的长度
        function<int(int)> dfs = [&](int x)
        {
            int maxLen = 0;
            for(int y : g[x])
            {
                int len = dfs(y) + 1;
                if(s[x] != s[y])
                {
                    ret = max(ret, maxLen + len);
                    maxLen = max(maxLen, len);
                }  
            }
            return maxLen;
        };
        dfs(0);
        // 由于本题求得是路径上节点的个数，所以要多加一
        return ret + 1;
    }
};